#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}
ListNode* partition(ListNode* pHead, int x) {
    // write code here
    ListNode* pcur = pHead;
    ListNode* newHead, * newTail;
    newHead = newTail = NULL;
    while (pcur)
    {
        if (pcur->val < x)
        {
            if (newHead == NULL)
            {
                newHead = newTail = pcur;
            }
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }

        }
        pcur = pcur->next;
    }
    if(newTail)
        newTail->next = NULL;
    pcur = pHead;
    while (pcur)
    {
        if (pcur->val >= x)
        {
            if (newHead == NULL)
            {
                newHead = newTail = pcur;
            }
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }

        }
        pcur = pcur->next;
    }
    if(newTail)
        newTail->next = NULL;
    return newHead;
}


int main()
{
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));
 
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;

    node1->val = 1;
    node2->val = 6;
    node3->val = 2;
    node4->val = 3;
    node5->val = 5;

    ListNode* plist = node1;
    partition(node1, 3);

	return 0;
}